#include "utils.h"

class Solution {
    public:
        ListNode *reverseBetween1(ListNode *head, int m, int n) {
            int k = n-m;
            ListNode *p = NULL, *q = head;
            if(m == 1) {
                for (int i = 0; i < k; ++i) {
                    p = q->next;
                    q->next = p->next;
                    p->next = head;
                    head = p;
                }
                return head;
            }
            m--;
            while(--m) q = q->next;
            p = q->next;
            ListNode *r;
            for (int i = 0; i < k; ++i) {
                r = p->next;
                p->next = r->next;

                r->next = q->next;
                q->next = r;
            }
            return head;
        }
        ListNode *reverseBetween(ListNode *head, int m, int n) {
            int k = n-m;
            ListNode **p = &head, *q, *r;
            while(--m) p = &((*p)->next);
            q = *p;
            while(k--) {
                r = q->next;
                q->next = r->next;

                r->next = *p;
                *p = r;
            }
            return head;
        }
};

int main(int argc, char *argv[])
{
    int a[] = {1,2,3,4,5,6,7};
    ListNode *p = make_list(a,sizeof(a)/sizeof(int));
    print_list(p);
    //Solution ss;
    //p = ss.reverseBetween(p,2,7);
    print_list(reverse_list(p));
    return 0;
}
